5. 最长回文子串

一、题目原型：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

二、题目意思剖析：

回文其实是对称的一个字符串。
比如：aba 、xyx、 mnnm、xoox 这样子。。。

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

输入: "cbbd"
输出: "bb"

三、解题思路：

中心法

官方解释：
事实上，只需使用恒定的空间，我们就可以在 O(n^2) 的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。
你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）。

我的理解：
我们根据对称的这个特性，来进行查找，以一个点为中心，两个指针左右移动，如果两边对应的字母相同，那么就继续移动，直到超出边界或者两边字母不同。

安排：

// 返回当前回文最大的长度
func haha(_ letters: [String],_ left: Int, _ right: Int) -> (Int) {
    
    var L:Int = left
    var R: Int = right
    
    // 当左边指针不小于0，当右边指针不超过字符串长度
    // 并且左右两个数值要相等
    while L>=0 && R<letters.count && letters[L] == letters[R] {
        L = L - 1
        R = R + 1
    }
    return R - L - 1
}

func longestPalindrome(_ s: String) -> String {
    
    var letters: [String] = []
    for char in s {
        let str: String = String.init(char)
        letters.append(str)
    }
    
    var start:Int = 0
    var end: Int = 0
    var huiwen: String = ""
    for i in 0..<letters.count {
        
        // 这分为两种情况：1.回文长度为奇数时，中心在中间那个字母
        //              2.回文长度为偶数时，中心在两个字母之间
        let len1: Int = haha(letters, i, i)
        let len2: Int = haha(letters, i, i+1)
        // 取最大值
        let len: Int = len1 > len2 ? len1 : len2
        
        if len > end - start {
            start = i - (len - 1) / 2
            end = i + len / 2
        }
    }
    
    for i in start..<end+1 {
        huiwen.append(letters[i])
    }
    return huiwen
}

四、小结

一切一切的算法，前提是要找到规律。然后一步一步剖析找出最好的算法。
在本题中，我的笔记思路只画出了一种情况，还有另一种情况就是回文长度为偶数时，中心在两个字母之间，也是一样的规律去找。最后比较这两种情况，找出最大值就行了。

耗时94毫秒，超过55.56%的提交记录，总提交数1056。

有其他好的方法请极速留言，非常乐意一起探讨。😄